package xyf.p04.tree;

import commons.TreeNode;

import java.util.HashMap;

/**
 * ClassName: P0105_BuildTree
 * Description:
 * Author: xyf
 * Date: 9/9/22 9:41 AM
 * Version: 1.0
 **/
public class P0105_BuildTree
{
    private HashMap<Integer, Integer> inOrderMap = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder)
    {
        for (int i = 0; i < inorder.length; i++)
        {
            inOrderMap.put(inorder[i], i);
        }

        return dfs(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }

    private TreeNode dfs(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight)
    {
        if (preLeft > preRight)
        {
            return null;
        }

        int rootNum = preorder[preLeft];

        TreeNode root = new TreeNode(rootNum);

        Integer inorderRootIndex = inOrderMap.get(rootNum);

        int leftLength = inorderRootIndex - inLeft;

        root.left = dfs(preorder, inorder, preLeft + 1, preLeft + leftLength, inLeft, inorderRootIndex - 1);

        root.right = dfs(preorder, inorder, preLeft + leftLength + 1, preRight, inorderRootIndex + 1, inRight);

        return root;
    }
}